This invention relates to a method and apparatus for classifying graphics segments to facilitate pick and display operation.
A computer-aided design (CAD) system may comprise a data base memory for storing information relating an an article whose design is being developed, e.g. an integrated circuit, a program memory for storing programs that are used in developing the design, a processor which acts on the stored information relating to the article in accordance with the stored programs for modifying the stored information, and a user interface whereby the user is able to control operation of the CAD system. Typically, the user interface comprises an input device for loading information into the data base memory, display apparatus for providing a display of the article represented by the contents of the data base memory, or some portion thereof, and a manipulation device for controlling the manner in which the stored programs act on the contents of the data base memory. The CAD system may also include, or be connected to, a printer or plotter for providing a hard copy of the display provided by the display apparatus.
A CAD system may employ a display system in which a picture to be displayed is composed of objects and data representing the objects is stored in the data base memory in the form of segments. A segment is a logically related collection of picture primitives that are operated upon as a single entity. Each segment comprises a segment header portion which includes a unique identification number, a segment body portion which includes picture primitives, for example a list of vectors specified by their end points in a rectangular Cartesian coordinate system, and a segment end portion. All segments in a picture are normally linked together into a structure called the display list. To locate any segment the display list is traversed until the desired segment is located.
In use of a CAD system, it is frequently necessary to carry out operations on an object. These operations might include altering the object or displaying the object at a enlarged scale so that the user can discern features of the object that cannot be clearly seen when the display represents the entire contents of the data base memory. The operation of selecting, or picking, the data segment that represents an object of interest is performed by displaying a cursor which is movable under user control by use of the manipulation device, which may be a joystick, a mouse or other manipulation device. If the user wishes to select the segment representing a particular object, the cursor is placed over the object on the display and a pick operation is performed. The segment may now be the subject of future operations, e.g. display at an enlarged scale. To locate the segment under the cursor during a pick operation a search is conducted in which each segment of the picture is examined in turn until a segment located under the cursor is found. This search may be accomplished by using the contents of the data base memory to draw a virtual, i.e., undisplayed, image in the address space of the display apparatus and carrying out a logical AND operation between the locations that are pixilated during this drawing operation and the location of the cursor. On average, N/2 segments need to be tested for cursor coverage, where N is the number of segments. Locating the cursor directly over the object of interest can be difficult. Therefore, pick operations can also be performed to find segments located within an area around the cursor. The area in which segments can be found is called a pick aperture. Pick operations are time consuming, and in the case of a large data base may take up to 30 seconds to complete. Such a delay is disturbing to the user of the CAD system. However, it is not practicable to keep a running check on the identity of the segment under the cursor as the cursor is moved through the picture, since this would entail continually updating the cursor segment at a high speed.
In a CAD system employing a segmented display, the display is not created directly from the segments stored in the data base memory, by continuously drawing a succession of vectors on the display screen. Rather, the contents of the data base memory are used to create a virtual image of the vectors in the address domain of a frame buffer and the contents of the frame buffer are used to drive a raster scan display device which displays the contents of the frame buffer. If the address space of the frame buffer is larger than the address domain occupied by the virtual image, the entire contents of the data base memory are represented in the display. If it is desired to display an object at an enlarged scale, the contents of the frame buffer must be changed. With a conventional CAD system having a segmented display, the contents of the data base memory are used to create a virtual image representing the entire contents of the data base memory over an enlarged address domain, with only the object of interest being within the address space of the frame buffer. Again, this is a time-consuming operation and may be disturbing to the user of the CAD system.
It has been observed that in most pictures that are displayed using a CAD system, the density with which information (represented by total vector length) is distributed over the picture area, both in the horizontal, or X, direction and in the vertical, or Y, direction, varies substantially in accordance with a Gaussian function. Therefore, half of the information content of the display is associated with values of X that are less than the value /X associated with the peak of the Gaussian function and half of the information content is associated with values of X that are greater than /X. Furthermore, one quarter of the information content of the display is associated with values of X that are less than /X-0.67 s.d.X (where s.d.X is the standard deviation in the X direction), one quarter with values of X between /X-0.67 s.d.X and /X, one quarter with values of X between /X and /X+0.67 s.d.X, and one quarter with values of X greater than /X+0.67 s.d.X. Similarly, in the Y direction one quarter of the information content of the display is associated with each of the four bands of the display characterized respectively by values of Y less than /Y-0.67 s.d.Y, between /Y-0.67 s.d.Y and /Y, between /Y and /Y+0.67 s.d.Y, and greater than /Y+0.67 s.d.Y.